package com.jn.algorithm.day028;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 江南大学1033190417
 * @date 2023/1/4 20:16
 */
public class Solution {

    private int count = 0;
    private int path = 0;

    public int numWays(int n, int[][] relation, int k) {
        dfs(0, n - 1, k, relation);
        return count;
    }

    public void dfs(int current, int target, int k, int[][] relation) {
        if (path == k && current == target) {
            count++;
            return;
        }
        if (path == k) {
            return;
        }
        for (int i = 0; i < relation.length; i++) {
            if (relation[i][0] == current) {
                path++;
                dfs(relation[i][1], target, k, relation);
                path--;
            }
        }
    }

    //以上是深度优先算法，下边是广度优先算法
    public int numWays2(int n, int[][] relation, int k) {
        return bfs(n, relation, k);
    }

    private static class Node {
        public int data;//结点的序号
        public int len = 0;//当前路径长度

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", len=" + len +
                    '}';
        }
    }

    public int bfs(int n, int[][] relation, int k) {
        int count = 0;
        Deque<Node> queue = new LinkedList<>();
        Node begin = new Node();
        begin.data = 0;
        begin.len = 0;
        queue.addFirst(begin);
        while (!queue.isEmpty()) {
            Node current = queue.removeFirst();
            if (current.data == n - 1 && current.len == k)
                count++;
            if (current.len == k)
                continue;
            for (int i = 0; i < relation.length; i++) {
                if (relation[i][0] == current.data) {
                    Node next = new Node();
                    next.data = relation[i][1];
                    next.len = current.len + 1;
                    queue.addFirst(next);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] relation = new int[][]{
                {0, 2},
                {2, 1},
                {3, 4},
                {2, 3},
                {1, 4},
                {2, 0},
                {0, 4}
        };
        System.out.println("=========" + solution.numWays2(5, relation, 3));
    }
}
